package likouJava;

import java.util.HashMap;

public class 从前序与中序遍历序列构造二叉树 {

    private HashMap<Integer, Integer> inorderIndexMap;
    private int preorderIndex = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //把中序遍历的值和索引保存到哈希表
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return build(preorder, 0 ,inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;

        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        //找到根在中序的位置
        int inorderIndex = inorderIndexMap.get(rootVal);

        //构造左子树
        root.left = build(preorder, left, inorderIndex -1);

        //构造右子树
        root.right = build(preorder, inorderIndex + 1, right);

        return root;
    }
}
